home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48_1 / list.set < prev    next >
Text File  |  1995-03-23  |  8KB  |  241 lines

  1. Article 1780 of comp.sys.handhelds:
  2. Path: en.ecn.purdue.edu!pur-ee!mentor.cc.purdue.edu!purdue!tut.cis.ohio-state.edu!cica!sol.ctr.columbia.edu!samsung!usc!apple!dan
  3. From: dan@Apple.COM (Dan Allen)
  4. Newsgroups: comp.sys.handhelds
  5. Subject: RPL Code for Lists/Sets, Rev 2
  6. Keywords: RPL,HP-48SX,lists,sets,set operations
  7. Message-ID: <40185@apple.Apple.COM>
  8. Date: 10 Apr 90 17:09:32 GMT
  9. References: <40175@apple.Apple.COM>
  10. Distribution: comp.sys.handhelds
  11. Organization: Apple Computer Inc, Cupertino, CA
  12. Lines: 225
  13.  
  14.  
  15.                     LIST and SET Operations for the HP-48SX
  16.                          By Dan Allen, 10 April 1990
  17.                                 Revision 2
  18.  
  19. LIST PROCESSING
  20.   The HP-48SX supports lists of objects as a built-in data type.  Several 
  21. functions are provided for working on lists:
  22.  
  23.     Function     Operation
  24.     --------     ---------
  25.     +            Concatenates two lists into one list
  26.     SIZE         Returns the number of elements in a list
  27.     POS          Checks if an element is in a list
  28.     SUB          Returns a subset of a list as a list
  29.     GET          Returns the nth element of a list
  30.     PUT          Replaces the nth element of a list
  31.  
  32. Other than direct editing of a list, there is no way to add elements to a list 
  33. other than by appending elements to the front or back of a list through the + 
  34. operator, and there is no way to delete elements of a list.
  35.   Here are a few list operations that extend the functionality of the HP-48SX.  
  36. Ideally these should be in a future machine; in the meantime they should be 
  37. written in assembly language for better efficiency.
  38.   The first two functions are CAR and CDR, named after the LISP functions of 
  39. the same bizarre but historically interesting names.  Common LISP also has the 
  40. functions FIRST and REST which are exactly the same as CAR and CDR, which 
  41. return the first and remaining parts of a list.  The second pair of functions 
  42. are INS and DEL, which allow inserting and deleting specific elements of a 
  43. list.
  44.   These routines handle invalid arguments quietly, i.e., deleting the 5th 
  45. element of a 4 element list does nothing; it returns the 4 element list 
  46. unchanged, without any error mentioned.  Similar handling of invalid 
  47. conditions is done by the other routines as well.
  48.  
  49. LISTS AS SETS
  50.   A list supports an ordering of its elements and can have duplicate members.  
  51. Sets are not ordered and can only have one occurance of a given object.  With 
  52. these restrictions, a list can be used as a set with various functions 
  53. designed to support set operations.  Such functions are provided here, with 
  54. many of the operations also being valid on lists as well.
  55.   ADJOIN allows items to be added to a set.  ADJOIN makes sure that no 
  56. duplicate entries are allowed in the list, thus enforcing one of the rules of 
  57. sets.
  58.   MEMBER tests set membership, that is, it checks to see if an object is 
  59. included in a set (or list).  It only searches the top level.  It returns a 
  60. CDR-like list beginning with the item found, or the empty list { } if the 
  61. object is not found.
  62.   UNION and INTERSECT implement set union and intersection, while DIFF and 
  63. SDIFF are set difference and symmetric difference.  If the lists given are not 
  64. sets (that is, they contain duplicates), duplicates may appear in the results.  
  65. These four operations are the main arithmetic operations for sets, with the 
  66. following similarities to arithmetic and boolean operations:
  67.  
  68.    ARITHMETIC            BOOLEAN            SET OPERATION
  69.    ----------            -------            -------------
  70.    addition (+)          OR (inclusive)     union
  71.    subtraction (-)       AND NOT            difference
  72.    multiplication (*)    AND                intersection
  73.    division (/)          XOR                symmetric difference
  74.  
  75. EXAMPLES
  76.  
  77. { 1 2 3 } CAR  -->  1                 { } CAR  -->  { }
  78. { 1 2 3 } CDR  -->  { 2 3 }           { } CDR  -->  { }
  79.  
  80. { 1 2 3 } 1 0 INS  -->  { 0 1 2 3 }   { 1 2 } 9999 48 INS  -->  { 1 2 48 }
  81. { 1 2 3 } 2 DEL  -->  { 1 3 }         { 1 2 } 9999 DEL  -->  { 1 2 }
  82.  
  83. { 1 2 3 } 2 MEMBER  -->  { 2 3 }      { 1 2 3 } 4 MEMBER  -->  { }
  84. { 1 2 } 3 ADJOIN  -->  { 1 2 3 }      { 1 2 3 } 3 ADJOIN  -->  { 1 2 3 }
  85.  
  86. { 1 2 } { 3 4 } UNION --> {1 2 3 4}   { 1 2 } { 1 2 } UNION  -->  { 1 2 }
  87. { 1 2 } { 3 4 } INTERSECT --> { }     { 1 2 } { 2 3 } INTERSECT  -->  { 2 }
  88. { 1 2 } { 3 4 } DIFF --> { 1 2 }      { 1 2 } { 2 3 } DIFF  -->  { 1 }
  89. { 1 2 } { 3 4 } SDIFF --> {1 2 3 4}   { 1 2 } { 2 3 } SDIFF  -->  { 1 3 }
  90.  
  91.   Comments are bracketed by @ signs.  With minor changes, most of these 
  92. programs should run on the HP-28.  Here then are some useful list and set 
  93. operations for the HP-48SX:
  94.  
  95. CAR   @ Extracts the first object of a list as an atomic entity @
  96. <<    @ USAGE:  list CAR  -->   obj   @
  97.   IF DUP SIZE THEN 1 GET END  @ CAR of empty list is an empty list @
  98. >>
  99.  
  100. CDR   @ Returns the tail (all but 1st object) of a list as a list @
  101. <<    @ USAGE:  list CDR  -->  list   @
  102.   OBJ->
  103.   IF DUP
  104.   THEN 1 - ->LIST SWAP DROP
  105.   ELSE DROP { }   @ CDR of an empty list is the empty list @
  106.   END
  107. >>
  108.  
  109. INS   @ Inserts an object as the nth element of list @
  110. <<    @ USAGE:  list integer obj INS  -->  list   @
  111.   -> list n x
  112.   <<
  113.     list 1 n 1 - SUB x + list n list SIZE SUB +
  114.   >>
  115. >>
  116.  
  117. DEL   @ Deletes the nth element of list @
  118. <<    @ USAGE:  list integer DEL  -->  list   @
  119.   -> list n
  120.   <<
  121.     list 1 n 1 - SUB list n 1 + list SIZE SUB +
  122.   >>
  123. >>
  124.  
  125. MEMBER  @ Checks if obj is a member of list at the top level @
  126. <<      @ USAGE:  list obj MEMBER  -->  list   @
  127.   -> list obj
  128.   <<
  129.     list obj
  130.     IF POS DUP 0 >
  131.     THEN list SWAP list SIZE SUB
  132.     ELSE DROP { }
  133.     END
  134.   >>
  135. >>
  136.  
  137. ADJOIN  @ Adds an object to a list, preventing duplicates @
  138. <<      @ USAGE:  list obj ADJOIN  -->  list   @
  139.   -> list obj
  140.   <<
  141.     IF list obj MEMBER SIZE
  142.     THEN list
  143.     ELSE list obj +
  144.     END
  145.   >>
  146. >>
  147.  
  148. UNION  @ Returns the set union of two lists (c = a OR b) @
  149. <<     @ USAGE:  list list UNION  -->  list   @
  150.   OVER -> a b c  @ efficiency tip: put smallest list on top of stack @
  151.   <<
  152.     IF a SIZE 0 == b SIZE 0 == OR
  153.     THEN a b +  @ if either list is empty then concatenate lists @
  154.     ELSE        @ step through the second list's elements @
  155.       b 1 1 b SIZE
  156.       START
  157.         GETI DUP c SWAP
  158.         IF POS
  159.         THEN DROP
  160.         ELSE 'c' SWAP STO+  @ adding appropriate new elements @
  161.         END
  162.       NEXT
  163.       DROP2 c 
  164.     END
  165.   >>
  166. >>
  167.  
  168. INTERSECT  @ Returns the set intersection of two lists (c = a AND b) @
  169. <<         @ USAGE:  list list INTERSECT  -->  list   @
  170.   { } -> a b c  @ efficiency tip: put smallest list on top of stack @
  171.   <<
  172.     IF a SIZE 0 == b SIZE 0 == OR
  173.     THEN c
  174.     ELSE
  175.       b 1 1 b SIZE
  176.       START
  177.         GETI DUP a SWAP
  178.         IF POS
  179.         THEN 'c' SWAP STO+
  180.         ELSE DROP
  181.         END
  182.       NEXT
  183.       DROP2 c
  184.     END
  185.   >>
  186. >>
  187.  
  188. DIFF  @ Returns the set difference of two lists (c = a AND NOT b) @
  189. <<    @ USAGE:  list list DIFF  -->  list   @
  190.   { } -> a b c
  191.   <<
  192.     IF a SIZE 0 == THEN c
  193.     ELSE IF b SIZE 0 == THEN a
  194.       ELSE
  195.         a 1 1 a SIZE
  196.         START
  197.           GETI DUP b SWAP
  198.           IF POS
  199.           THEN DROP
  200.           ELSE 'c' SWAP STO+
  201.           END
  202.         NEXT
  203.         DROP2 c
  204.       END
  205.     END
  206.   >>
  207. >>
  208.  
  209. SDIFF  @ Returns the set symmetric difference between two lists (c = a XOR b) 
  210. @
  211. <<     @ USAGE:  list list SDIFF  -->  list   @
  212.   { } -> a b c   @ Efficiency note: this is O(n^2) and could be improved @
  213.   <<
  214.     IF a SIZE 0 == THEN b         @ if a is empty, then return b @
  215.     ELSE IF b SIZE 0 == THEN a    @ if b is empty, then return a @
  216.       ELSE                        @ else loop through both lists @
  217.         a 1 1 a SIZE     
  218.         START
  219.           GETI DUP b SWAP
  220.           IF POS
  221.           THEN DROP
  222.           ELSE 'c' SWAP STO+
  223.           END
  224.         NEXT
  225.         DROP2
  226.         b 1 1 b SIZE
  227.         START
  228.           GETI DUP a SWAP
  229.           IF POS
  230.           THEN DROP
  231.           ELSE 'c' SWAP STO+
  232.           END
  233.         NEXT
  234.         DROP2 c
  235.       END
  236.     END
  237.   >>
  238. >>
  239.  
  240.  
  241.